package org.jpropelleralt.universe.impl;

import java.util.Collections;
import java.util.IdentityHashMap;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.Map.Entry;
import java.util.concurrent.locks.ReentrantLock;
import java.util.logging.Logger;

import javax.swing.event.ChangeListener;

import org.jpropelleralt.box.Box;
import org.jpropelleralt.change.Change;
import org.jpropelleralt.change.ChangeDispatchSource;
import org.jpropelleralt.change.ChangeDispatcher;
import org.jpropelleralt.change.impl.ChangeDispatcherSwing;
import org.jpropelleralt.concurrency.Responder;
import org.jpropelleralt.concurrency.impl.CoalescingResponder;
import org.jpropelleralt.reaction.Reaction;
import org.jpropelleralt.universe.Universe;
import org.jpropelleralt.universe.UniverseInternal;
import org.jpropelleralt.utils.impl.IdentityHashSet;
import org.jpropelleralt.utils.impl.LoggerUtils;
import org.jpropelleralt.view.View;

/**
 * Default implementation of {@link Universe}
*/
public class UniverseDefault implements Universe, ChangeDispatchSource {
	
	private final Logger logger = LoggerUtils.logger(UniverseDefault.class);
	
	private final UniverseInternalDefault internal = new UniverseInternalDefault();
	
	/**
	 * This stores the changes made during the CURRENT propagation process, while that
	 * propagation is being performed. Since this map is cleared after the end of
	 * each propagation event, and is used to work out when propagation is complete,
	 * it ensures that even when we coalesce the changes caused by multiple propagations,
	 * we still fully propagate each one.
	 * To give an example, say we have a {@link Box} X, and a {@link Box} C
	 * that is calculated based on X. Now we do the following:
	 * 
	 * 1. Change X
	 * 2. Read C
	 * 3. Change X again
	 * 4. Read C
	 * 
	 * If these actions are all done quickly, then changes will be coalesced - the changes
	 * from step 2 and step 4 will be added together in the allChanges map. This is required
	 * since we want to dispatch at some stage after 4, passing all changes that have happened
	 * up to that point.
	 * 
	 * Note how C works - when stage 2 occurs, we will cause C to recalculate itself (it will have noticed
	 * the change in X at stage 1, invalidating its state, so 2 causes recalculation). At this point,
	 * C now has a valid cache. 
	 * 
	 * Now consider what can go wrong. When stage 3 occurs - if we were to look at ONLY the allChanges map,
	 * we would now see that we already had a change to X, so we don't bother to propagate the new
	 * change. Hence C never sees the new change, and does not invalidate its cache again at stage 3.
	 * Now when we read C at stage 4, it gives us the old, out of date value it calculated at stage 2,
	 * NOT the new value from the value of X set in stage 3.
	 * 
	 * To avoid this, we start with a fresh, empty currentChanges map on every propagation. Then in
	 * stage 3, this map does NOT have a change for X, and when we get the new change to X, we propagate
	 * it fully. As we do this, the new changes that are part of the propagation are built up in the
	 * currentChanges map. When the propagation is complete, these new changes are then used to extend
	 * the coalesced changes in allChanges. The contract for {@link Change} specifies that change extension
	 * must be associative, so it is safe to combine the changes in the "wrong" operation order (obviously NOT
	 * in the wrong order of operands, since change extension is NOT required to be commutative).
	 * 
	 * We use an {@link IdentityHashMap} so that we show the change to each INSTANCE,
	 * we don't care about equality, we need identicality
	 */
	private Map<Box, Change> currentChanges = 
		new IdentityHashMap<Box, Change>();

	private Map<Box, Change> currentChangesUnmodifiable = Collections.unmodifiableMap(currentChanges);
	
	/**
	 * This stores all changes made to each {@link Box} since the last successful
	 * dispatch. Where the changes from multiple propagations (of multiple initial changes)
	 * are coalesced, the merging of changes is performed into this map, from currentChanges,
	 * at the end of propagation. See the docs for the currentChanges map for a more detailed
	 * explanation of this process, and the reason it is necessary. 
	 * 
	 * We use an {@link IdentityHashMap} so that we show the change to each INSTANCE,
	 * we don't care about equality, we need identicality
	 */
	private Map<Box, Change> allChanges =
		new IdentityHashMap<Box, Change>();

	/**
	 * Stores pending reactions on each {@link Box}
	 */
	private Map<Box, Set<Reaction>> pendingReactions = new IdentityHashMap<Box, Set<Reaction>>();
	
	/**
	 * Stores pending reactions that have an unknown target {@link Box}
	 */
	private Set<Reaction> pendingReactionsOnUnknown = new IdentityHashSet<Reaction>();
	
	/**
	 * Unmodifiable view of allChanges, to be handed out to {@link ChangeDispatcher}s.
	 */
	private Map<Box, Change> allChangesUnmodifiable = Collections.unmodifiableMap(allChanges);
	
	/**
	 * User to actually call change method on {@link ChangeListener}s
	 */
	private ChangeDispatcher dispatcher;
	
	/**
	 * This lock is always held during dispatching.
	 * This is used to detect when a thread is dispatching, and
	 * calls prepareChange. This is the same as detecting when a {@link ChangeListener} responds
	 * to a {@link ChangeListener#change(List, Map)} by trying (possibly indirectly) to
	 * change a {@link Changeable} - which is prohibited.
	 */
	private final ReentrantLock dispatchingLock = new ReentrantLock();

	/**
	 * This lock is required to read, write, change listeners on any {@link Changeable},
	 * and to dispatch changes, or obviously to prevent other threads from doing these things. 
	 */
	public final ReentrantLock mainLock = new ReentrantLock();
	
	/**
	 * Update by dispatching
	 */
	private final Responder dispatchUpdater = new CoalescingResponder(new Runnable() {
		@Override
		public void run() {
			dispatch();
		}
	});
	
	//Track the reactions that have been used in the current propagation
	private final IdentityHashSet<Reaction> usedReactions = new IdentityHashSet<Reaction>();

	/**
	 * Create a {@link UniverseDefault} using a default {@link ChangeDispatcher} 
	 */
	public UniverseDefault() {
		this(new ChangeDispatcherSwing());
	}
	
	/**
	 * Create a {@link UniverseDefault} 
	 * @param dispatcher		The {@link ChangeDispatcher} used to actually 
	 * 							pass changes to {@link View}s
	 */
	public UniverseDefault(ChangeDispatcher dispatcher) {
		super();
		this.dispatcher = dispatcher;
		dispatcher.setSource(this);
	}
	
	@Override
	public void prepareDispatch() {
		
		//Get main lock
		mainLock.lock();
		
		//Only one dispatcher - this thread
		dispatchingLock.lock();
	}

	@Override
	public void concludeDispatch() {
		try {
			//Clear the changes dispatcher has just dealt with
			allChanges.clear();
		} finally {		
			//Release locks in reverse order
			dispatchingLock.unlock();
			leaveMainLock();
		}
	}
	
	/**
	 * Dispatch any changes to listeners
	 */
	private void dispatch() {
		//Make sure we are locked - prevents any more changes occuring while dispatcher dispatches
		enterMainLock();
		try {
			//Dispatch changes to listener, if we have any
			if (!allChanges.isEmpty()) {
				
				//Apply any unknown reactions, in case they produce any extra changes we will
				//need to dispatch
				//Note that reactions with unknown targets are ALWAYS triggered by other changes,
				//hence we know that we will have some changes in allChanges map, leading to
				//a dispatch call and the chance to apply the extra unknown reactions.
				//Applying the unknown reactions here means we get the benefit of coalescing - 
				//we may avoid multiple applications of the reactions by waiting until a dispatch
				//is needed - this can actually be quite a large efficiency improvements, making
				//the otherwise inefficient unknown-target reactions a good deal more efficient.
				internal.applyReactionsWithUnknownTargets();
				
				//Now we can ask dispatcher to dispatch
				dispatcher.dispatch();
			}
		} finally {
			leaveMainLock();
		}
	}

	private void enterMainLock() {
		mainLock.lock();
	}
	private void leaveMainLock() {
		mainLock.unlock();
	}
	
	//Provide changes to our ChangeDispatcher
	@Override
	public Map<Box, Change> changes() {
		return allChangesUnmodifiable;
	}
	
	@Override
	public UniverseInternal internal() {
		return internal;
	}

	private class UniverseInternalDefault implements UniverseInternal {
		
		private boolean propagating = false;
		
		@Override
		public void prepareWrite(Box box) {
			//Only the thread that is currently dispatching (if any) can hold the
			//dispatchingLock. Hence if we hold it here, it indicates that a we 
			//have dispatched a change to a ChangeListener, and it has responded
			//by attempting to make another change to a Changeable. This is illegal
			//since it can cause loops, out of order changes, etc.
			//NOTE we can check this without further locking since it
			//is only checking for THIS thread holding the lock, so no
			//other concurrent thread can affect this between us checking, and 
			//acquiring the mainLock
			if (dispatchingLock.isHeldByCurrentThread()) {
				throw new IllegalArgumentException("Must not attempt to change a Changeable in response to a change - this can cause cycles and is prohibited.");
			}

			//Acquire necessary lock
			mainLock.lock();
		}

		@Override
		public void propagateWrite(Box box, Change change) {
			//TODO use specific exception here
			//We must have the necessary lock here
			if (!mainLock.isHeldByCurrentThread()) {
				throw new IllegalMonitorStateException("Cannot propagateWrite without first calling prepareWrite (lock must be held when calling propagateWrite)");
			}
			
			//TODO use specific exception here
			//Check that the current changes map is empty - should have 
			//been cleared at end of last propagation
			if (!currentChanges.isEmpty()) {
				logger.severe("IMPLEMENTATION: Non-empty current changes when propagation started - invalid state.");
				throw new IllegalArgumentException("Non-empty current changes when propagation started - invalid state.");
			}
			
			//Extend change to initial, using current changes map
			Change extendedInitialChange = extendChange(box, change, currentChanges);

			//We are now propagating, so reading is illegal
			propagating = true;
			
			//If the box has actually got an extended change, start recursive processing from that box
			if (extendedInitialChange != null) { 
				processReactions(box, change);
			}

			//Propagation is complete
			propagating = false;
			
			//We need to coalesce the currentChanges into allChanges
			currentChangesToAllChanges();
		}

		private void processReactions(Box box, Change change) {
			//Process each reaction on the changed box
			for (Reaction reaction : box.features().reactions()) {
				
				//Ask reaction to apply itself, given current changes
				Map<Box, Change> extraChanges = reaction.react(currentChangesUnmodifiable);
				
				//Remember we have used this reaction 
				usedReactions.add(reaction);

				//Process all changes from the reaction
				for (Entry<Box, Change> entry : extraChanges.entrySet()) {

					Box reactionBox = entry.getKey();
					Change reactionChange = entry.getValue();

					//If the key is null, handle an unknown-target change
					if (reactionBox == null) {
						pendingReactionsOnUnknown.add(reaction);
						
					//Handle known target
					} else {
						//Add reaction to those pending for box
						addPendingReaction(reactionBox, reaction);
						
						//Extend the change for the affected box to cover the new change as well, using current changes map
						Change extendedChange = extendChange(reactionBox, reactionChange, currentChanges);
						
						//If we have extended the change then notify listeners of the listener
						if (extendedChange != null) {
							processReactions(reactionBox, reactionChange);
						}
					}
				}
			}
		}
		
		private void addPendingReaction(Box box, Reaction reaction) {
			Set<Reaction> reactionSet = pendingReactions.get(box);
			if (reactionSet == null) {
				reactionSet = new IdentityHashSet<Reaction>();
				pendingReactions.put(box, reactionSet);
			}
			reactionSet.add(reaction);
		}
		
		private void currentChangesToAllChanges() {
			
			//First, tell any reactions that have been used
			//in the propagation about the complete change map,
			//building a set of any that need to be applied immediately
			Set<Reaction> immediateReactions = new IdentityHashSet<Reaction>();
			for (Reaction reaction : usedReactions) {
				if (reaction.completeChanges(currentChanges)) {
					immediateReactions.add(reaction);
				}
			}
			
			//Done with these now
			usedReactions.clear();
			
			for (Box key : currentChanges.keySet()) {
				Change currentChange = currentChanges.get(key);
				
				//Extend the change in the allChanges map
				extendChange(key, currentChange, allChanges);
			}
			
			//We have now coalesced the changes, can clear current changes map
			currentChanges.clear();
			
			//Now let the immediate reactions apply
			for (Reaction reaction : immediateReactions) {
				boolean wasUnknown = pendingReactionsOnUnknown.remove(reaction);
				//Remove the reaction from any other pending lists
				for (Set<Reaction> otherReactions : pendingReactions.values()) {
					otherReactions.remove(reaction);
				}
				reaction.apply(wasUnknown);
			}
		}
		
		/**
		 * Extend the current change for a {@link Changeable}
		 * in the changes map.
		 * This either extends the current change if there is one, OR
		 * adds the new change if there is no current change.
		 * @param box
		 * 		The {@link Changeable} whose {@link Change} is to be extended
		 * @param newChange
		 * 		The new {@link Change} for the {@link Changeable}
		 * @param changes
		 * 		The {@link Change} map
		 * @return
		 * 		If the change for the listener is extended, the
		 * change it was extended to is returned.
		 * If the existing change already covered the new change (so
		 * no extension needs to take place), null is returned
		 */
		private Change extendChange(Box box, Change newChange, Map<Box, Change> changes) {
			//See if we have a current change for this listener
			Change currentChange = changes.get(box);
			
			//Make the extended change
			//	If we have no current change, just use the new one
			//	If we have a current change, extend the new change to cover
			//		itself AND the current change, and use that extended change.
			Change changeToUse;
			if (currentChange == null){
				changeToUse = newChange;
			} else {
				//Note that extend will return null if the new change is already covered
				changeToUse = newChange.extend(currentChange);
			}
			
			//If we have extended the change (or we are using the new one directly)
			//then put it in the map
			if (changeToUse != null) {
				//Put the new change for changeable
				changes.put(box, changeToUse);
			}
			
			//Return the extended change if there is one, or null if the existing change is large enough
			return changeToUse;
		}
		
		@Override
		public void concludeWrite(Box box) {
			//Release necessary lock
			leaveMainLock();
			
			//dispatch();
			//If we have left mainLock completely, it is safe to
			//request a dispatch. Note that there is no reason to request a
			//dispatch yet if we still hold the mainLock - we will request
			//one when we DO release the mainLock
			if (!mainLock.isHeldByCurrentThread()) {
				dispatchUpdater.request();
			}		
		}

		@Override
		public void acquire() {
			mainLock.lock();
		}

		@Override
		public void release() {
			leaveMainLock();
			
			//We need to request dispatch since it may not have been requested
			//while the mainLock was held
			if (!mainLock.isHeldByCurrentThread()) {
				dispatchUpdater.request();
			}
		}
		
		private void applyReactionsWithUnknownTargets() {
			//First, keep applying any pending unknown-target reactions
			//until there are none left. We need to do this repeatedly in
			//case any reactions trigger other reactions.
			//FIXME would be useful to detect cycles here.
			while (!pendingReactionsOnUnknown.isEmpty()) {
				Reaction unknownReaction = pendingReactionsOnUnknown.iterator().next();
				pendingReactionsOnUnknown.remove(unknownReaction);
				
				//Remove the reaction from any other pending lists
				for (Set<Reaction> otherReactions : pendingReactions.values()) {
					otherReactions.remove(unknownReaction);
				}
				
				//DO propagate - since targets are unknown, changes have NOT been accounted for.
				unknownReaction.apply(true);
			}
		}
		
		@Override
		public void prepareRead(Box box) {
			enterMainLock();
			
			//We cannot read when propagating
			if (propagating) {
				throw new IllegalArgumentException("Must not read any state while propagating changes through reactions.");
			}
			
			//FIXME
			//try applying reactions in order they were added - add to maps AND to some kind of FIFO set. (If reaction added twice, gets priority from first time added)
			
			//Apply any unknown reactions, in case they affect this box
			applyReactionsWithUnknownTargets();
			
			//Find reactions for this box
			Set<Reaction> reactions = pendingReactions.get(box);
			
			//If no reactions, nothing to do
			if(reactions == null) {
				return;
			}
			
			//Now completely clear the reactions for this box
			//by just removing the entire set from pendingReactions map
			pendingReactions.remove(box);
			
			//If the same reactions are pending for any other boxes,
			//clear them out. This won't hit the "reactions" set we
			//are using, since we removed it from pendingReactions map.
			for (Set<Reaction> otherReactions : pendingReactions.values()) {
				otherReactions.removeAll(reactions);
			}
			
			//Now we need to make sure we apply all the reactions we had pending
			//for the specific box being read - they may make changes to other Boxes as well,
			//this is fine
			for (Reaction reaction : reactions) {
				//Don't propagate - change was already propagated when Box was written,
				//triggering each reaction in the first place
				reaction.apply(false);
			}
		}
		
		@Override
		public void concludeRead(Box box) {
			leaveMainLock();
		}
		
		//These methods are simple - they just use the main lock.
		@Override
		public void prepareViewChange(Box box) {
			enterMainLock();
		}
		@Override
		public void concludeViewChange(Box box) {
			leaveMainLock();
		}
		@Override
		public void prepareReactionChange(Box box) {
			enterMainLock();
		}
		@Override
		public void concludeReactionChange(Box box) {
			leaveMainLock();
		}
	}
	
}
